package com.aqie.hard.divideAndConquer;


import com.aqie.libs.StdOut;
import org.apache.commons.lang3.ArrayUtils;

import java.util.Arrays;

/**
 *
 * @Function: 312 每当你戳破一个气球 i 时，你可以获得 nums[left] * nums[i] * nums[right] 个硬币
 * 你可以假设 nums[-1] = nums[n] = 1，但注意它们不是真实存在的所以并不能被戳破。
 * @Author: aqie
 * @Date: 2019/8/24 10:21
 */
public class MaxCoins {
    /**
     * 1. 动态规划  21，ms
     * @param nums
     * @return
     */
    public static int maxCoins(int[] nums) {
        int length = nums.length;
        int n = length + 2;
        int[] nums2 = new int[n];
        System.arraycopy(nums,0,nums2,1,length);
        nums2[0] = 1; nums2[n-1] = 1;

        // 初始化 n*n 二维数组
        int[][] dp = new int[n][n];
        // 这里不能按行打表
        // 只能按长度打表, dp[i][j], j-i >= 2
        for (int len = 2; len < n; ++len) {
            for (int i = 0; i < n - len; ++i) {
                int j = i + len;
                for (int k = i + 1; k < j; ++k) {
                    dp[i][j] = Math.max(dp[i][j], nums2[i] * nums2[k] * nums2[j] + dp[i][k] + dp[k][j]);
                }
            }
        }
        return dp[0][n-1];
    }


    public static void main(String[] args) {
        int[] bullons = {3,1,5,8};
        StdOut.println(maxCoins(bullons));      // 167
        addArray();
    }

    /**
     * 数组拷贝四种方式
     * clone
     * System.arraycopy
     * Arrays.copyOf
     * Arrays.copyOfRange
     */
    public static void addArray(){
        int[] arr = {1,2,3};
        /*int[] add = ArrayUtils.add(arr, 4);
        int[] add1 = ArrayUtils.insert(0,add, 0);*/


        // 数组拷贝
        int[] ans = new int[5];
        System.arraycopy(arr,0,ans,1,3);
        StdOut.print(Arrays.toString(ans));
    }
}
